package at.fhooe.mc.task01;

import java.util.Arrays;

/**
 * @author Johannes Huber-Ecker, MC13017
 */

public class BinarySearchTree {

	private static boolean isFirst = false;

	/** Inner class for the binary tree node. **/
	protected class BinaryTreeNode {

		public BinaryTreeNode left;
		public BinaryTreeNode right;
		public int data;

		public BinaryTreeNode(int elem) {
			data = elem;
			left = null;
			right = null;
		}
	}

	/** Root node of the tree. **/
	protected BinaryTreeNode root;

	/** Number of elements stored in the tree. */
	protected int size;

	/**
	 * Inserts the given element. Duplicate elements are not allowed. Returns
	 * true if insertion was successful, false otherwise.
	 * 
	 * @param elem
	 *            the data, which we insert in the tree
	 * @return true, when the insert was successful, false when the number
	 *         allready exist in the tree
	 */
	public boolean insert(int elem) {

		boolean ret = add(root, null, false, elem);
		if (ret == true) {
			size = size + 1;
		}
		return ret;
	}

	/**
	 * Helper method for insert
	 * 
	 * @param t
	 *            is the position of the actual knot
	 * @param parent
	 *            is the knot before (parent)
	 * @param right
	 *            is boolean to know set the right or left knot
	 * @param d
	 *            is the new data of the knot
	 * @return true or false, true -> when the insert was successful, false ->
	 *         otherwise (e.g. the number already exist in the tree)
	 */
	protected boolean add(BinaryTreeNode t, BinaryTreeNode parent,
			boolean right, Integer d) {
		if (t == null) {
			BinaryTreeNode n = new BinaryTreeNode(d);
			// for the first knot
			if (root == t) {
				root = n;
				return true;
			}
			// set the right knot
			if (right)
				parent.right = n;
			// set the left knot
			else
				parent.left = n;
			return true;
			// if the number already exist in the tree
		} else if (t.data == d) {
			return false;
		} else if (d.compareTo(t.data) < 0) {
			return add(t.left, t, false, d);
		} else {
			return add(t.right, t, true, d);
		}
	}

	/**
	 * Searches for the (first) element with the given key. Returns true if it
	 * could be found, false otherwise.
	 * 
	 * @param key
	 *            the data which is search in the tree
	 * @return ah boolean data, true -> the number is in the tree, false -> the
	 *         number is not in the tree
	 */
	public boolean find(int key) {

		return contains(root, key);
	}

	/**
	 * Helper method for find
	 * 
	 * @param t
	 *            is the actual knot
	 * @param c
	 *            is the data, who is searched
	 * @return ah boolean data, true -> the number is in the tree, false -> the
	 *         number is not in the tree
	 */
	protected boolean contains(BinaryTreeNode t, Integer c) {

		if (t == null)
			return false;
		if (t.data == c)
			return true;
		if (c.compareTo(t.data) < 0)
			return contains(t.left, c);
		return contains(t.right, c);
	}

	/**
	 * Removes the element with the given key. Returns true if the key could be
	 * found (and removed), false otherwise.
	 * 
	 * @param key
	 *            the data which is delete in the tree
	 * @return boolean true or false; true when the number was founded and
	 *         delete, false the number doesn`t exist in the tree
	 */
	public boolean remove(int key) {

		return remove(root, key);
	}

	/**
	 * Helper method to remove
	 * 
	 * @param t
	 *            the place of the knot
	 * @param d
	 *            the number, who is to delete
	 * @param st
	 *            actual knot
	 * @param par
	 *            parent of the knot
	 * @return boolean true or false; true when the number was founded and
	 *         delete, false the number doesn`t exist in the tree
	 */
	public boolean remove(BinaryTreeNode t, Integer d) {
		BinaryTreeNode n, st, par, succ;
		par = null;
		st = t;
		while ((st != null) && !(st.data == d)) {
			par = st;
			if (d.compareTo(st.data) < 0)
				st = st.left;
			else
				st = st.right;
		}
		n = st;
		if (n == null)
			return false;
		if (n.right == null) {
			// no right son
			st = n.left;
		} else if (n.right.left == null) {
			// right son has no left son
			st = n.right;
			st.left = n.left;
		} else {
			// right son has left son
			succ = n.right;
			while (succ.left.left != null)
				succ = succ.left;
			st = succ.left;
			succ.left = st.right;
			st.left = n.left;
			st.right = n.right;
		}
		if (par == null)
			root = st;
		else if (d.compareTo(par.data) < 0)
			par.left = st;
		else
			par.right = st;
		size = size - 1;
		return true;
	}

	/**
	 * Returns the number of elements stored in the tree.
	 * 
	 * @return the size of the tree (all dates)
	 */
	public int size() {

		return (size);
		// return getSize(root);
	}

	// i have written this method, but we don`t need it :-/
	/**
	 * Helper method for size()
	 * 
	 * @param t
	 *            the know of the actual place in the tree
	 * @return the size of the tree
	 */
	protected int getSize(BinaryTreeNode t) {
		if (t == null) {
			return 0;
		}
		return 1 + getSize(t.left) + getSize(t.right);
	}

	/**
	 * Returns the parent element of the given key. Integer.MIN_VALUE if no
	 * parent can be found.
	 * 
	 * @param key
	 *            is the number, from which we search the parent
	 * @return when the number exist and have ah parent, the data of the parent,
	 *         otherwise Interger.Min_Value
	 */
	public int getParent(int key) {

		int x = getParent(null, root, key);
		return x;
	}

	/**
	 * Helper method for getParent
	 * 
	 * @param a
	 *            the knot before
	 * @param b
	 *            the actual knot, where you are
	 * @param c
	 *            the data of the knot, which you search the parent
	 * @return the data of the parent
	 */
	protected int getParent(BinaryTreeNode a, BinaryTreeNode b, Integer c) {

		if (b == null)
			return Integer.MIN_VALUE;
		if (b.data == c) {
			if (root.data == c) {
				return Integer.MIN_VALUE;
			}
			return a.data;
		}
		if (c.compareTo(b.data) < 0) {
			return getParent(b, b.left, c);
		}
		return getParent(b, b.right, c);
	}

	/**
	 * Returns the elements of the tree in ascending (inorder traversal) or
	 * descending (reverse inorder traversal) order.
	 * 
	 * @param ascending
	 *            is boolean, true -> inorder, false -> reverse inorder
	 * @return ah array of all knots in the tree
	 */
	public int[] toArray(boolean ascending) {

		StringBuffer buffer = new StringBuffer();
		isFirst = true;
		// helper method
		arrayHelper(buffer, root);

		String[] splittArray = buffer.toString().split("\\, ");

		int[] array = new int[size];
		for (int i = 0; i < size; i++) {
			array[i] = Integer.parseInt(splittArray[i]);
		}

		if (ascending == true) {
			return array;
		}
		// reverse order
		int temp;
		for (int i = 0; i < size / 2; i++) {
			temp = array[i];
			array[i] = array[size - 1 - i];
			array[size - 1 - i] = temp;
		}
		return array;
	}

	/**
	 * helper method for to Array
	 * 
	 * @param buffer
	 *            in the StringBuffer they were written all dates, seperate by
	 *            ah ", "
	 * @param t
	 *            the position of the actual knot
	 */
	protected void arrayHelper(StringBuffer buffer, BinaryTreeNode t) {

		if (t == null)
			return;
		arrayHelper(buffer, t.left);
		if (isFirst) {
			isFirst = false;
		} else {
			buffer.append(", ");
		}
		buffer.append(t.data);
		arrayHelper(buffer, t.right);
	}

	/**
	 * Returns the elements of the tree (postorder traversal).
	 * 
	 * @return ah array with all elements in the tree in postorder
	 */
	public int[] toArrayPostOrder() {

		StringBuffer buffer = new StringBuffer();
		isFirst = true;
		// helper method
		arrayHelperPostOrder(buffer, root);

		String[] splittArray = buffer.toString().split("\\, ");

		int[] array = new int[size];
		for (int i = 0; i < size; i++) {
			array[i] = Integer.parseInt(splittArray[i]);
		}
		return array;
	}

	/**
	 * Helper method for toArrayPostOrder
	 * 
	 * @param buffer
	 *            StringBuffer where all dates of the knots where saved;
	 * @param t
	 *            the position of the actual knot
	 */
	protected void arrayHelperPostOrder(StringBuffer buffer, BinaryTreeNode t) {

		if (t == null)
			return;
		arrayHelperPostOrder(buffer, t.left);
		arrayHelperPostOrder(buffer, t.right);
		if (isFirst) {
			isFirst = false;
		} else {
			buffer.append(", ");
		}
		buffer.append(t.data);
	}

	/**
	 * Returns the elements of the tree (preorder traversal).
	 * 
	 * @return ah array with all elements of the tree in in preorder
	 */
	public int[] toArrayPreOrder() {

		StringBuffer buffer = new StringBuffer();
		isFirst = true;
		// helper method
		arrayHelperPreOrder(buffer, root);

		String[] splittArray = buffer.toString().split("\\, ");

		int[] array = new int[size];
		for (int i = 0; i < size; i++) {
			array[i] = Integer.parseInt(splittArray[i]);
		}
		return array;
	}

	/**
	 * Helper method for toArrayPreOrder
	 * 
	 * @param buffer
	 *            StringBuffer where all dates of the knots where saved;
	 * @param t
	 *            the position of the actual knot
	 */
	protected void arrayHelperPreOrder(StringBuffer buffer, BinaryTreeNode t) {

		if (t == null)
			return;
		if (isFirst) {
			isFirst = false;
		} else {
			buffer.append(", ");
		}
		buffer.append(t.data);
		arrayHelperPreOrder(buffer, t.left);
		arrayHelperPreOrder(buffer, t.right);
	}

	/**
	 * Returns largest number stored in the tree. Integer.MIN_VALUE if no
	 * largest element can be found
	 * 
	 * @return the largest number which is stored in the tree
	 */
	public int max() {

		if (root == null) {
			return Integer.MIN_VALUE;
		}
		int x = root.data;
		BinaryTreeNode t = root;
		while (t.right != null) {
			t = t.right;
			x = t.data;
		}
		return x;
	}

	/**
	 * Returns smallest number stored in the tree. Integer.MIN_VALUE if no
	 * smallest element can be found
	 * 
	 * @return the smallest number, which is stored in the tree
	 */
	public int min() {

		if (root == null) {
			return Integer.MIN_VALUE;
		}
		int x = root.data;
		BinaryTreeNode t = root;
		while (t.left != null) {
			t = t.left;
			x = t.data;
		}
		return x;
	}

	/** Represents the tree in a human readable form. */
	public String toString() {

		StringBuffer buffer = new StringBuffer();
		appendString(buffer, root, 0);
		return buffer.toString();
	}

	/**
	 * Helper method for toString
	 * 
	 * @param buffer
	 *            StringBuffer where all dates of the knots where saved;
	 * @param t
	 *            the position of the actual knot
	 * 
	 * @param indent
	 *            save the number of the insertion
	 */
	protected void appendString(StringBuffer buffer, BinaryTreeNode t,
			int indent) {

		if (t == null)
			return;
		appendString(buffer, t.right, indent + 2);
		for (int i = 0; i < indent; i++) {
			buffer.append("  ");
		}
		buffer.append(t.data);
		buffer.append("\n");
		appendString(buffer, t.left, indent + 2);
	}

	// little extra from FPS Exercise 5
	/**
	 * this method balance the "BinarySearchTree"/balanceTree
	 */
	public void balance() {
		if (root != null) {
			int[] sortedTree = this.toArray(true);
			root = null;
			size = 0;
			balanceRecursive(sortedTree);
		}
	}

	/**
	 * Recursive helper method for balance This method insert always the mid of
	 * the actual sorted tree -> its make ah balance tree
	 * 
	 * @param sortedTree
	 *            is the array with the numbers to insert.
	 */
	public void balanceRecursive(int[] sortedTree) {

		if (sortedTree.length == 1) {
			insert(sortedTree[0]);
			return;
		}

		// to insert always the mid of the list
		this.insert(sortedTree[sortedTree.length / 2]);
		int[] left = Arrays.copyOfRange(sortedTree, 0, sortedTree.length / 2);
		int[] right = Arrays.copyOfRange(sortedTree, sortedTree.length / 2,
				sortedTree.length);

		balanceRecursive(left);
		balanceRecursive(right);
	}
}